package com.example.hot100;

import com.example.tree.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
 *  你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
 *
 *  示例 1:
 * 输入:
 * 	Tree 1                     Tree 2
 *           1                         2
 *          / \                       / \
 *         3   2                     1   3
 *        /                           \   \
 *       5                             4   7
 * 输出:
 * 合并后的树:
 * 	     3
 * 	    / \
 * 	   4   5
 * 	  / \   \
 * 	 5   4   7
 */
public class Leetcode617_MergeTrees {
    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(3);
        root1.right = new TreeNode(2);
        root1.left.left = new TreeNode(5);

        TreeNode root2 = new TreeNode(2);
        root2.left = new TreeNode(1);
        root2.right = new TreeNode(3);
        root2.left.right = new TreeNode(4);
        root2.right.right = new TreeNode(7);

        TreeNode newRoot = new Solution().mergeTrees(root1, root2);
        System.out.println(Solution.layerOrder(newRoot));

    }

    static class Solution {
        public static List<Integer> layerOrder(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            Deque<TreeNode> queue = new LinkedList<>();
            if (root == null) return res;
            queue.offer(root);

            while (!queue.isEmpty()) {
                TreeNode tmp = queue.poll();
                res.add(tmp.val);
                if (tmp.left != null) queue.offer(tmp.left);
                if (tmp.right != null) queue.offer(tmp.right);
            }

            return res;
        }

        /**
         * dfs2
         * @param root1
         * @param root2
         * @return
         */
        private TreeNode mergeTrees3(TreeNode root1, TreeNode root2) {
            if (root1 == null) return root2;
            if (root2 == null) return root1;
            TreeNode merged = new TreeNode(root1.val + root2.val);
            merged.left = mergeTrees3(root1.left, root2.left);
            merged.right = mergeTrees3(root1.right, root2.right);
            return merged;
        }

        /**
         * 解法二:dfs方式
         * @param root1
         * @param root2
         * @return
         */
        private TreeNode mergeTrees2(TreeNode root1, TreeNode root2) {
            if (root1 == null && root2 == null) return null;
            TreeNode newRoot;
            if (root1 != null && root2 != null) {
                newRoot = new TreeNode(root1.val + root2.val);
                newRoot.left = mergeTrees2(root1.left, root2.left);
                newRoot.right = mergeTrees2(root1.right, root2.right);
            } else if (root1 == null) newRoot = root2;
            else newRoot = root1;
            return newRoot;
        }

        /**
         * BFS方式
         * @param root1
         * @param root2
         * @return
         */
        private TreeNode mergeTrees1(TreeNode root1, TreeNode root2) {
            if (root1 == null) return root2;
            if (root2 == null) return root1;
            TreeNode newRoot = new TreeNode(root1.val + root2.val);
            Deque<TreeNode> mergedQueue = new LinkedList<>();
            Deque<TreeNode> queue1 = new LinkedList<>();
            Deque<TreeNode> queue2 = new LinkedList<>();
            mergedQueue.offer(newRoot);
            queue1.offer(root1);
            queue2.offer(root2);

            while (!queue1.isEmpty() && !queue2.isEmpty()) {
                TreeNode tmp = mergedQueue.poll();
                TreeNode tmp1 = queue1.poll();
                TreeNode tmp2 = queue2.poll();
                TreeNode left1 = tmp1.left, right1 = tmp1.right;
                TreeNode left2 = tmp2.left, right2 = tmp2.right;

                if (left1 != null || left2 != null) {
                    if (left1 != null && left2 != null) {
                        tmp.left = new TreeNode(left1.val + left2.val);
                        queue1.offer(left1);
                        queue2.offer(left2);
                        mergedQueue.offer(tmp.left);
                    } else if (left1 == null) tmp.left = left2;
                    else tmp.left = left1;
                }

                if (right1 != null || right2 != null) {
                    if (right1 != null && right2 != null) {
                        tmp.right = new TreeNode(right1.val + right2.val);
                        queue1.offer(right1);
                        queue2.offer(right2);
                        mergedQueue.offer(tmp.right);
                    } else if (right1 == null) tmp.right = right2;
                    else tmp.right = right1;
                }
            }

            return newRoot;
        }

        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
            return mergeTrees1(root1, root2);
        }
    }
}
